ひねられた無向グラフの重み付けされていないグラフをトラバースする：各ノードの最小訪問数

Question

無向グラフ、重み付けされていないグラフをトラバースするコードを作成しようとしています。本質的に、メソッドはノード（すべての隣接ノードを知っている）を渡されます。次に、この方法は、ノードからノードへ移動し、ノードが互いにリンクする情報を収集することによって、グラフのモデルを効率的に構築しなければならない*。最後に、このメソッドには、すべてのノードとそれらを接続するすべての頂点の完全なリストがあります。

*問題の要点は効率的に言葉にあり、私がそれを意味するものです。私はこの小さなグラフにあなたの注意を向けてみましょう：

するのは、私は私が最小限に抑えたいC、B、F、D、H、JまたはEを訪問することができますいずれかのノードでG.を開始しましょう私がノードにアクセスした回数、ノードを訪問するためには、そのノードに向かう途中のすべてのノードを通過する必要があります。

例：次のノードはA、B、F、D、H、J、Eのいずれかになります。ただし、A以外のノードを訪問するには、非効率的であると考えられるGを再び通過する。 Aを訪問するには、GとCをもう一度訪問し、Cを通過してGを通過してグラフの残りの部分に戻る必要があります。だから、私はAに行くことにしました。これは、Gに到達するためにCを再び通過しなければならないことを意味します。したがって、論理的な観点からは、最後にCブランチを訪れるのは理にかなっています。

ただし、プログラムがノードGで開始するとき、分岐Cがデッドエンドにつながることは認識しません。私はこれを書いているので、それは不可能かもしれないと思うが、とにかく尋ねる：与えられた情報のみを使って、できるだけ効率的にこのグラフを横断することがある（すなわち、ノードは、その訪問し、エッジはそれらのノードから出てくる？それとも私はちょうど私がすべてのノードを訪れる保証するために変動ダイクストラのアルゴリズムで行くべき？

ことが重要ならばこれは、すべてJavaで記述されます。

Answer 1

全体のグラフ（取得したパスに関係なく）を計算し、各ノードで何らかの操作を行うか、あるノードから他のノードへの最短パスを計算しますか？ （私はあなたの目標を理解していないかもしれません）

最初のケースでは、Breadth First Searchのようなトラバーサルアルゴリズムに固執します。もう1つの場合は、同じ重み付きエッジ（つまり= 1）を使用してDijkstraと考えることができます。

1つの開始ノードだけに興味があり、すべてのエッジの重さが同じ場合、BFSはダイクストラの特別なケースとして見ることができます。異なるコストで、統一原価検索を使用することができます。

Answer 2

集合引数で単純な再帰だけではないでしょうか？

public void traverse(Node n, Set<Node> visisted) { 

    visited.add(n); 

    for (Node neighbour : n.getNeighbours()) { 

    if (!visited.contains(neighbour)) { 
     traverse(neighbour, visited); 
    } 

    } 

} 

Answer 3

興味深い問題ですが、元の問題/目標が最新の応答から何であるかはっきりしていません。

これは有効な問題の再記述ですか？：各ノードを訪問

目的：

制約を要する最小限にルートを計画：

• 開始ノードが
• 指定されている各ノードを訪問するコストは「1」
• 目的であります
• アルゴリズムは、すべてのコストが発生する前にグラフを完全に把握しています（すべての可能なパスを検索しても、それ自体はコストがかかりません）

それが正しい場合は、これらの観察を考慮して、あなたの問題の「読み」：

• 「ノードを訪問」するための費用は「1」であれば、それはコスト」と同じです「ノードを訪問する」と「エッジを横切る」との間に1対1の対応関係があるので、「任意のエッジをトラバースする」は「1」である。
• 2つのノードが直接接続されていない場合でも、介在するノードを単純にトラバースすることができるため、「transitively が接続されています。」と表示されます。 は、（代わりに：あなたは「あなたが ノードを再訪問しないかもしれません」制約を持ってないように見える。）

したがって：すべてのノードがいくつかの「距離」を経由して「接続」されている、とあなたはすべて訪問したいです移動した「距離」を最小限に抑えます。

これは間違いありませんか？

もしそうなら、あなたの問題はほぼ「伝統的なセールスマン問題」であると提出します。私が見る唯一の違いは、TSPの記述では「開始ノードと終了ノードが同じであること」が必要なことがあることです。しかし、私は思っています - 開始ノードと終了ノードを違うものにすることができます。

もしこれが正しいとすれば、あなたは本当に効率的な方法でTSPを "解決"しようとしています - そして、同じことをやろうとしているあなたの先にいる多数に参加してください！単純に「すべての組み合わせを試し、それぞれをスコア化し、最小限に抑える」よりも優れた解決策はありません。

Answer 4

これはU

package capgemni; 
/** 
* 
* @author amit 
*/ 
public class Graphtraversing { 
public static void main(String[] args) { 
    int res = 0; 
    String[] input1= {"A", "B", "C", "D"}; 
    int[] input2 = {4, 8, 6, 3, 3, 5}; 

    res = minimum_cost(input1, input2); 
    System.out.println(res); 

} 
static int minimum_cost(String[] input1,int[] input2) 
{ 
    int d = input1.length; 
    int costmatrix[][]=new int[input1.length][input1.length]; 
    int i=0,j=0,k=0; 


    for(i=0;i<input1.length;i++){ 
    for(j=i;j<input1.length;j++){ 
     costmatrix[i][j]=0; 
    } 
    } 

    for(i=0;i<input1.length;i++){ 
    for(j=i;j<input1.length;j++){ 
     if(i==j){ 
     costmatrix[i][j] = 0; 
     } 
else{ 
     costmatrix[i][j] = input2[k]; 
     k++; 
} 

    } 
    } 

for(i=0;i<input1.length;i++){ 
for(j=0;j<input1.length;j++){ 
    costmatrix[j][i] = costmatrix[i][j]; 
} 
} 

int cost = 0; 
int mcost = 0; 
int first = 1; 
for(i=0; i<input1.length; i++){ 

for(j=0; j<input1.length; j++){ 

    cost = cost + costmatrix[i][j]; 

} 
if(first == 1){ 
mcost = cost; 
first = 0; 
} 
else if(cost < mcost){ 
mcost = cost; 
} 
cost = 0; 
} 


    return mcost; 
} 
}