最長片道きっぷの経路を求める
最長片道きっぷの経路を求める Index & Overview あらまし この文書は、ＪＲの最長片道きっぷの経路を、 整数計画法と全探索の２つの方法で求めた過程をまとめたものです。 前者では厳密に、後者ではややイイカゲンに、その経路を求めることに成功し、 ２つの方法で求めた経路は一致しました。 トピックス NHK の紀行番組「列島縦断 鉄道12000kmの旅」をきっかけにこの Web ページを探し当てた方は、まず「付録２（2004年３月版）」をご覧ください。 現状の最長片道きっぷの経路や、ありそうな質問をまとめてあります。 ふと思い立って、2006年５月版の最長片道きっぷ経路図（PDF 形式、35,414 bytes）を作りました。 2004年３月版の地図との相違点はただ１点、 「富山港線を削除した」ことです（2006年２月28日廃止）。 もともと最長経路に含まれていなかった路線が廃止にな
分数切除平面法(ゴモリーカット)の頂点彩色問題への適用
明治大学理工学部情報科学科 計算理論研究室 中田 寛基 概要 巡回セールスマン問題(TSP)などの難しい問題を解く手法の一つに、数理計画法というものがある。その手法を、定式化した彩色問題に応用できないかを考える。 研究背景、目的 CPLEX(Iloｇ社)などの数理計画問題ソルバーが強力になってきている。 巡回セールスマン問題(TSP)などにおいて、数理計画法(と分枝限定などの組み合わせ)が良い成績を残している。 その数理計画法を学び他の問題に応用できないかを考える。 彩色問題が整数計画法に定式化できるので、より高速に解を求めたい。 彩色問題以外にも、整数計画法に定式化できる問題に対するアプローチの開発にもつながるはずである。 内容 数理計画法について 分数切除平面法(ゴモリーカット)について 頂点彩色問題の定式化 実験結果 参考資料 「オペレーションズ・リサーチ」 森雅夫、松井知己 経営シ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
