2024-03-28T22:58:59Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000319622023-04-27T10:00:04Z01164:02592:02633:02635
制約付き最短路問題に対する実験的解析Experimental Analysis for Constrained Shortest Path Problemjpnhttp://id.nii.ac.jp/1001/00031962/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=31962&item_no=1&attribute_id=1&file_no=1Copyright (c) 2002 by the Information Processing Society of Japan上智大学理工学部機械工学科宮本, 裕一郎本稿では,移動に要する費用の和が与えられた上限以下でなければならないという条件の下で,始点から終点への最短パスを見つける最短路問題を扱う.これは制約付き最短路問題と呼ばれるものの1つでありNP-困難である.その問題に対し擬多項式時間厳密解法を提案する.併せて計算実験の結果も報告する.計算実験に用いた問題例は最大で点数4900 ,枝数約20000である.In this paper, we examine the constrained shortest path problem. This is the problem of finding a path from a source to a destination such that the sum of the costs on the path satisfies the cost constraint and minimize the sum of the travel time. The problem is known to be NP-hard. We present a pseudopolynomial algorithm for solving the problem. Computational results are presented for the computational time of problems involving up to 4900 vertices, about 20000 edges.AN1009593X情報処理学会研究報告アルゴリズム(AL)200288(2002-AL-086)35422002-09-192009-06-30