問題タブ [answer-set-programming]

次を生成するルールがあります

次の部分は、5,1 で始まり、5,3 で終わるルートです。

ルート内(x1,y1,x2,y2)

• x1 = 最初の点の x 座標
• y1 = 最初の点の y 座標
• x2 = 2 点目の x 座標
• y2 = 2 点目の y 座標

これらのルートが交差しないように制約を書きたいのですが、この問題へのアプローチ方法がわかりません。この件で何か助けていただければ幸いです。

私の課題: グラフの色付け - グラフに 4 色が含まれているかどうかを確認するための回答セット プログラムを作成します。ぬりえがない場合は、答えが設定されていません。プログラムは、4 色塗りを行うコードとサンプル グラフ表現で構成する必要があります。

私はこれを持っています (ASP Graph Coloring Wikipedia から) が、それがどのように機能するのか正確にはわかりません - 誰かがこのコードを説明してもらえますか?

my current code aims to sum some values from a given database and select a combination of breakfast, lunch and dinner food. under the little database for testing you can find my code that is running and finding 42 answers for my given intervals. then i wanted to calculate also the other columns (proteis, fat, carbohydrates) as you can see directly below. but i am having some huge performance issues. the code is just not running (i waited one hour but no results showed up) is there any may to simplify the sum-chain sum_prot_fat_carb_bf /+lu /+di ? so that my program will finally run....im running out of ideas with this programming language. i would be glad if you could help me out. best regards

追加の制約 - 時間枠で TSP 問題を解決しようとしています。

すべての標準的な仮定が適用されます。

• 指定された都市で開始および終了します。
• 各都市は 1 回だけ訪れます。
• 移動コスト (ここでは移動時間) の観点から最適な経路を見つけようとします。

さらに、各都市には独自の時間枠の形式があります、都市を訪問できる時間を制限します。

• 閉園時間後の都市への訪問はできません。
• 開店時間前にどの都市にも到着し、開店を待つことができます。その場合、待ち時間は全体の経過時間に加算されますが、移動に費やされた時間には加算されません。したがって、 time_spent_travellingとtotal_time_passedは、追跡する必要がある 2 つの異なるものです。

total_time_passedに関して最適解を見つける制約を書くことができましたが、最適なtime_spent_travellingを見つける必要があります。

ここに私の論理があります：

そして、ここにサンプルデータがあります (clingo で実行するには ~ 30 秒かかります):

MAX 関数を使用して、実際の到着時間または都市の営業時間のいずれか遅い方を選択して、特定の都市への到着時間を計算しました。それはうまく機能したので、最初に考えたのは、この行を次のように変更して、場所のファクトに追加のフィールドを追加することでした:

このようにして、 location はtime_spent_travellingとtotal_time_passedの両方に関する情報を保持します。これは 5 つの都市では問題なく機能しますが、20 の都市では計算が長すぎます (15 分後にあきらめました)。プログラムは両方の状況でほぼ同時に実行されると予想していましたが、どうやらここで理解できないことがあります。 .

待機時間も別の事実として保存しようとしましたが、計算時間に同じように影響しているようで、#minimize 関数でそれを考慮するという別の問題が発生し、解決できませんでした。

だからここに私の質問があります：

• time_spent_travellingの最適値を計算するにはどうすればよいですか?ただし、待機時間を正しく考慮していますか?
• 上記で説明したように、コードの小さな変更が、なぜ解決プロセスにこれほど大きな計算上の影響を与えるのでしょうか?

最近 clingo を使い始めましたが、この問題に対する簡単な解決策が見つからない可能性が高いです。宣言型プログラミングに慣れすぎて、プログラムの書き方を変えるのはちょっと難しいです。

私が提供したコードは、クリンゴで簡単に実行できます。 clingo logic data

私の出力：

ここでの結果は、この特定の例では 9 である待機時間を考慮に入れています (378 は移動のみに費やされた時間です)。