PHPで学ぶ「集合知プログラミング」〜最適化〜 1

グループ旅行問題を特にあたり$peopleのarrayに人名と出発地を入れる。
そして、全ての人達の目的地としてLGAを設定する。
サンプルのフライトデータとしてhttp://kiwitobes.com/optimize/schedule.txtが用意されているのでダウンロードして同じディレクトリに入れておく。
そして、schedule.txtからoriginとdestをキーとしたフライトリストを作る。
さらに、HH:MMの形式で表された時間を午前０時０分から何分経ったかに変換するgetminutes関数を定義する

	$people = array(array('Symour', 'BOS'), array('Franny', 'DAL'), array('Zooey', 'CAK'), array('Walt', 'MIA'), array('Buddy', 'ORD'), array('Les', 'OMA'));
	$destination = 'LGA';
	$flights = array();
	$fp = fopen("schedule.txt", "r");
	while($line = fgets($fp)) {
	$line = rtrim($line);
	$explode_line = explode(",",$line);
	$origin = $explode_line[0];
	$dest = $explode_line[1];
	$depart = $explode_line[2];
	$arrive = $explode_line[3];
	$price = $explode_line[4];
	if(!isset($flights[$origin][$dest])){
	$flights[$origin][$dest] = array();
	}
	$flights[$origin][$dest][] = array($depart, $arrive, $price);
	}
	function getminutes($t) {
	$x = strptime($t, '%H:%M');
	return $x["tm_min"] + $x["tm_hour"]*60;
	}

view raw PHPで学ぶ集合知プログラミング5.1 hosted with ❤ by GitHub

誰がどの便でLGAにやってくるかを$sで表現する。
各数字はその日の何便目に乗るか。そして、Seymourの行き・帰り・Frannyの行き・帰り・・・の順に並んでいる。
この数列から各人の旅程の情報を出力する関数を定義する（printschedule）

	$s = array(1,4,3,2,7,3,6,3,2,4,5,3);
	function printschedule($r, $people, $flights, $destination) {
	$d = count($r)/2;
	for($i = 0; $i < $d; $i++){
	$name = $people[$i][0];
	$origin = $people[$i][1];
	$out = $flights[$origin][$destination][$r[($i*2)]];
	$ret = $flights[$destination][$origin][$r[($i*2+1)]];
	echo sprintf("%10s%10s %5s-%5s $%3s %5s-%5s $%3s" . PHP_EOL, $name, $origin, $out[0], $out[1], $out[2], $ret[0], $ret[1], $ret[2]);
	}
	}

view raw PHPで学ぶ集合知プログラミング5.2 hosted with ❤ by GitHub

コスト関数の定義。運賃総額と空港での待ち時間、レンタカーの追加料金を含めたコストを旅程ごとに算出する関数を定義する。

	function schedulecost($sol, $origin, $people, $flights, $destination) {
	$totalprice = 0;
	$latestarrival = 0;
	$earliestdep = 24*60;
	$d = count($sol)/2;
	for ($i = 0; $i < $d; $i++) {
	$origin = $people[$i][1];
	$outbound = $flights[$origin][$destination][$sol[$i*2]];
	$returnf = $flights[$destination][$origin][$sol[$i*2+1]];
	$totalprice += $outbound[2];
	$totalprice += $returnf[2];
	if ($latestarrival < getminutes($outbound[1])) {
	$latestarrival = getminutes($outbound[1]);
	}
	if ($earliestdep > getminutes($returnf[0])) {
	$earliestdep = getminutes($returnf[0]);
	}
	}
	$totalwait = 0;
	for ($i = 0; $i < $d; $i++) {
	$origin = $people[$i][1];
	$outbound = $flights[$origin][$destination][$sol[$i*2]];
	$returnf = $flights[$destination][$origin][$sol[$i*2+1]];
	$totalwait += $latestarrival - getminutes($outbound[1]);
	$totalwait += getminutes($returnf[0]) - $earliestdep;
	}
	if ($latestarrival < $earliestdep) {
	$totalprice += 50;
	}
	return $totalprice + $totalwait;
	}
	$totalcost = schedulecost($s, $origin, $people, $flights, $destination);
	var_dump($totalcost);

view raw PHPで学ぶ集合知プログラミング5.3 hosted with ❤ by GitHub