Truy vết đường đi trong đồ thị, cấu trúc lưu các đường đi?

dt2it153

Member
14/7/11
92
2
8
nhà tui ^^

link hình: http://www.mediafire.com/?gbgjd45yqybj5jw
Mình xây dựng class đại diện cho từng nút trog hình, gọi là class GraphNode.
Bình thường nếu chỉ có 1 đường đi từ A đến G, thì trong class GraphNode mình chỉ cần khai báo thêm thuộc tính:
Code:
protected GraphNode previous;
dùng để lưu đỉnh trước đỉnh đó.
vd như trong hình thì đỉnh trước đỉnh B là A --> code:
PHP:
B.previous = A;
Khi đó nếu muốn truy vết đường đi từ A đến G mình chỉ cần viết 1 hàm nthe này:
PHP:
public static List<String> findLongestPath(GraphNode des) { //des đại diện cho đỉnh đích đến G
List<String> path = new ArrayList<>();
        for(GraphNode v = des; v != null; v = v.previous) {
            path.add(v.val);
        }
        Collections.reverse(path);
return path;
}
là truy ra được đường đi từ A đến G.

Nhưng giả sử như trong hình, ta có 3 đường đi từ A đến G, đó là:
- A --> B --> D --> F --> G.
- A --> C --> D --> F --> G.
- A --> C --> E --> G.
Mình có thể dùng cấu trúc gì hoặc lưu như thế nào để có thể truy vết dc 3 đường đi này?
Theo như mình code trong thuật toán của mình thì lần đầu, nó tìm dc 1 đường, nó lưu lại D.previous = B. Sau đó nếu nó tìm dc 1 đường nữa, nó lại gán D.previous = C.
Mình đã thử thay biến previous trong class GraphNode thành biến mảng trong class GraphNode, nhưng ko xử lý cho ổn dc!
Ý mình là làm sao nó lưu dc B và C này là đỉnh trước D mà khi truy vết lại thì ko bị nhầm đường? Tại vì nếu không phải như trong hình thì trước B và C là các đỉnh khác nhau chứ ko fai đỉnh A.

p/s: cái này là mình viết thay đổi thuật toán Dijkstra, thay vì tìm đường ngắn nhất thì mình tìm đường dài nhất, nhưng ko fai là 1 đường mà là nhiều đường có cùng giá trị max này (nếu có).
Các bạn chỉ cho mình làm sao để lưu được các đỉnh đứng trước 1 đỉnh này. Vd như ở trên là lưu đỉnh B và C trước D, lưu sao mà khi truy ngược lại đường đi không bị nhầm lẫn.

http://en.wikipedia.org/wiki/Dijkstra's_algorithm#Pseudocode

link trên là đoạn mã giả thuật toán Dijkstra. Mình đang cố gắng thay đổi đoạn dưới đây để khi tìm dc 1 giá trị max khác thì nó lưu cái đỉnh của đường dài nhất khác đó:
Code:
for each neighbor v of u:                              // where v has not yet been
19                                                                                removed from Q.
20              alt := dist[u] + dist_between(u, v) ;
21              if alt < dist[v]:                                  // Relax (u,v,a)
22                  dist[v] := alt ;
23                  previous[v] := u ;            //dùng cái gì khác để lưu các đỉnh???
24                  decrease-key v in Q;
đoạn trên mình convert sang code java, dc viết trong 1 hàm sau:
PHP:
public void go() {
        while (this.priorityQ.hasMore()) {
            GraphNode n = this.priorityQ.remove();
            for (Edge e : n.getOutGoingEdges()) { //getOutGoingEdges() trả về các đỉnh kề với đỉnh n
                GraphNode adjNode = e.getNode();
                Integer newPossiblePathCost = e.getCost() + n.getDistance();
                if (newPossiblePathCost < adjNode.getDistance()) {
                    adjNode.setDistance(newPossiblePathCost);
                    adjNode.previous = n; //lưu node trước node adjNode, cần thay đổi????
                    this.priorityQ.updateGraphNodeDistance(adjNode); //cập nhật adjNode vào vị trí thích hợp trog priorityQ
                }
                //if(newPossiblePathCost == adjNode.getDistance()) {
                ///???????????
                //}
            }
        }
    }
Mong các bạn hướng dẫn!
 

infoboy

Member
12/1/11
34
16
8
Mình chưa xem xét kỹ giải thuật của bạn nên không chắc chắn với giải thuật đó áp dụng trong bài toán này liệu có chính xác hay không??
Giả sử là đúng đi mình có 1 ý tưởng thế này thấy có vẻ cũng hợp lý sẽ trình bày cho bạn tham khảo nếu có sai thì cũng góp phần giúp bạn tìm ra đc hướng đi đúng (thất bại là mẹ thành công :D)

- Mình bổ sung vào class GraphNode của bạn thuôc tính sau
Code:
protected GraphNode next;
Cái tên nói lên tất cả rồi, nó dùng để lưu cái node phía sau nó trên đường đi

- Trong chương trình mình tạo 1 biến global:
Code:
  ArrayList<GraphNode> result;
Biến này dùng để lưu tất cả các node xuất hiện trong các kết quả của bài toán.

-Method go() của bạn mình sẽ viết lại như thế này

Code:
public void go() {
      while (this.priorityQ.hasMore()) {
          GraphNode n = this.priorityQ.remove();
          for (Edge e : n.getOutGoingEdges()) { //getOutGoingEdges() trả về các đỉnh kề với đỉnh n
            GraphNode adjNode = e.getNode();
            Integer newPossiblePathCost = e.getCost() + n.getDistance();
            if (newPossiblePathCost < adjNode.getDistance()) {
                  adjNode.setDistance(newPossiblePathCost);
                  adjNode.previous = n; //lưu node trước node adjNode, cần thay đổi????
                  n.next = adjNode;
                  result.add(n);
             }
          //if(newPossiblePathCost == adjNode.getDistance()) {
              ///???????????
          //}
    }
  }
  }
- Nếu chạy OK thì cuối cùng kết quả result (phỏng đoán thôi - mình lấy lại các kết quả mà bạn chỉ ra ở trên): A A A B C C D D E F F G G G (thứ tự có thể khác nhau gì đấy mình không chắc chắn - nhưng chắc chắn với các con đường mà bạn tìm được ở trên thì 3 kết quả đầu luôn là A)

- Cuối cùng truy vết (ở đây mình sẽ truy vết xuôi): Mình nói ý tưởng thôi nhá trong khi list còn phần tử lấy phần tử đầu tiên ra khỏi list, xong rồi cứ next lấy phần tử tiếp theo ra khỏi list...đến lúc đến đích là G (hoặc next là null). Việc này giúp tìm được 1 đường đi, lại quay lại nếu list vẫn còn phần tử lại lấy node đầu tiên ra khỏi list rồi lại ->next.... Cuối cùng node của đường nào sẽ vào đường nấy.!

Hy vọng cách làm đúng!
 
  • Like
Reactions: dt2it153

dt2it153

Member
14/7/11
92
2
8
nhà tui ^^
- Cuối cùng truy vết (ở đây mình sẽ truy vết xuôi): Mình nói ý tưởng thôi nhá trong khi list còn phần tử lấy phần tử đầu tiên ra khỏi list, xong rồi cứ next lấy phần tử tiếp theo ra khỏi list...đến lúc đến đích là G (hoặc next là null). Việc này giúp tìm được 1 đường đi, lại quay lại nếu list vẫn còn phần tử lại lấy node đầu tiên ra khỏi list rồi lại ->next.... Cuối cùng node của đường nào sẽ vào đường nấy.!

Hy vọng cách làm đúng!
Hi, cuối cùng cũng có người wan tâm thread này of mình :D. Thank infoboy, có phải ý bạn là dựa vào cái next đấy nên tự động đường nào node nào nhớ node đi sau nó có đúng ko?
Để mh check thử nhé. Sáng mai mh cho infoboy biết kết quả. ;)
 

dt2it153

Member
14/7/11
92
2
8
nhà tui ^^
Hi infoboy, mình đã test thử cách của cậu nhưng có chút vấn đề.
trong result chứa 4 phần tử, đó là: A, A, A và C. Trong mỗi phần tử đó có next chứa phần tử tiếp theo của nó.
Nên điều kiện là trong khi list còn phần tử, sau mỗi lần tìm xong 1 đường, lưu lại, remove phần tử đó khỏi result sẽ bị lỗi.
Nên mình đã đổ các node có liên quan dựa vào next của mỗi phần tử trong result ra 1 List listTemp. Rồi dùng điều kiện để lấy chúng ra, nhưng ngặt cái ra sai đường đi rồi, có lẽ do điều kiện chưa đúng nhưng không biết sửa sao?
Code:
protected void tim(GraphNode des) {
        ArrayList<String> listTemp = new ArrayList();
        int k = 0;
        while (k < result.size()) {
            for (GraphNode node = result.get(k); node != null; node = node.next) {
                listTemp.add(node.val);
            }
            k++;
        }
        for(int i = 0; i < listTemp.size(); i++) {
            System.out.print(listTemp.get(i) + " ");
        }
 
        Vector<Vector> vPathsCollection = new Vector();
        while (!listTemp.isEmpty()) {
            Vector<String> vAPath = new Vector();
            for (int i = 0; i < listTemp.size() && (!listTemp.get(i).equals(des.val) || !listTemp.isEmpty()); i++) { //có lẽ điều kiện ở đây chưa đúng??!?
                if(i != 0) {
                vAPath.add(listTemp.get(i-1));
                listTemp.remove(i-1); //remove nó ra thì khi end for trog listTemp chỉ còn các ptu của các đường đi khác cần xét
                }
                else {
                    vAPath.add(listTemp.get(i));
                    listTemp.remove(i);
                }
            }
            vPathsCollection.add(vAPath);
        }
for (int j = 0; j < vPathsCollection.size(); j++) {
            System.out.println("Con duong " + j + ": ");
            for (int i = 0; i < vPathsCollection.get(j).size(); i++) {
                System.out.print(vPathsCollection.get(j).get(i) + "-");
            }
            System.out.println();
        }
    }
Cậu có ý gì giúp mình sửa lỗi này ko?
 

infoboy

Member
12/1/11
34
16
8
Mình nghĩ thế này nhé nếu làm theo cách của cậu thì cái listTemp sẽ có rất nhiều kết quả 1 số ví dụ:
A-> B -> D -> F -> G
B->D->F->G
D->F->G
F->G
A->C->D->F->G
C->D->F->G
D->F->G
F->G
...................................
Cậu muốn lấy được kết quả là đường đi từ A->G
Vậy cậu chỉ cần kiểm tra đường nào bắt đầu từ A đồng thời kết thúc ở G thì mới tiến hành tru vết, tức là thế này (minh không biết cậu dựa trên tiêu trí nào để đánh giá 2 node = nhau nên mình cứ so sánh chung chung với A và G nhé c code lại chi tiết sau)
Code:
while (k < result.size())
{
  for (GraphNode node = result.get(k); node != null; node = node.next) {
  listTemp.add(node.val);
  }
  k++;

for(int i = 0; i < listTemp.size(); i++) {
                System.out.print(listTemp.get(i) + " ");
}

if(listItem.get(0).equal("A") && listItem.get(listItem.size() - 1).equals("G")){
// Tien hanh cac thao tác truy vết
}
}
 

dt2it153

Member
14/7/11
92
2
8
nhà tui ^^
không phải đâu infoboy à. Cái listTemp nó như thế này nè:
A --> B --> D --> F --> G --> A --> B --> D --> F --> G --> A --> C --> D --> F --> G --> C --> E.
Là vậy đấy, cho nên mình mới xử lý tìm cách cho nó get ra từng đường, nhưng chua xử lý đúng. Không biết cậu có nick yahoo ko, tiện ra đấy mh trao đổi nhe.
 

infoboy

Member
12/1/11
34
16
8
Sr lâu mình không dùng yahoo nên remove mất rồi, c xem lại chỗ code mình mới sửa đi, khác của cậu mà, mình cho tất cả vào trong vòng while(k < result.size()){} đấy chứ
 

dt2it153

Member
14/7/11
92
2
8
nhà tui ^^
Sr lâu mình không dùng yahoo nên remove mất rồi, c xem lại chỗ code mình mới sửa đi, khác của cậu mà, mình cho tất cả vào trong vòng while(k < result.size()){} đấy chứ
Mình hiểu ý cậu, nhưng ở đây mình gặp tí vấn đề.
Cậu xem link hình sau nhe: http://www.mediafire.com/view/?87g32yc3cr73wf4
Hình này chi tiết hơn ở chỗ các cạnh có trọng số, như trong code mình trình bày, nó đại diện cho cost của cạnh đó. Hàm go():
PHP:
public void go() {
      while (this.priorityQ.hasMore()) {
          GraphNode n = this.priorityQ.remove();
          for (Edge e : n.getOutGoingEdges()) { //getOutGoingEdges() trả về các đỉnh kề với đỉnh n
            GraphNode adjNode = e.getNode();
            Integer newPossiblePathCost = e.getCost() + n.getDistance(); //tính toán lại giá trị cost mới
            if (newPossiblePathCost < adjNode.getDistance()) {
                  adjNode.setDistance(newPossiblePathCost);
                  adjNode.previous = n;
                  n.next = adjNode;
                  result.add(n);
            }
          //if(newPossiblePathCost == adjNode.getDistance()) {
              ///???????????
          //}
    }
  }
  }
Như đoạn code trên, n.getDistance() get ra khoảng cách từ 1 đỉnh đến đỉnh n. Vì vậy khi chạy hàm go() này, sẽ xảy ra tình trạng sau, cậu chú ý giá trị cost trong hình mh đính kèm nha:
lần chạy while đầu tiên, get n ra khỏi queue, n là đỉnh v1. Lấy ra các đỉnh liên kết với v1, ta có v2 và v3.
Trong for, lần 1, lấy v2 ra so sánh, newPossiblePathCost = 2, ta set dc v1.next = v2, đưa v1 vào result.
Lần 2, lấy v3 ra so sánh, vì newPossiblePathCost = 5, ta set v1.next = v3, tiếp tục đưa v1 vào result.
Các bước sau tương tự thế..
Ở đây mình chú ý 2 dòng in đậm đó, v1 lưu giá trị next sau cùng là v3, nên mình sẽ bị mất đường đi từ v1 đến v5 thông qua v2. Vậy ở đây mình cần xử lý ntn để nó lưu dc cái đường kia?
Thứ 2, thuật toán của mình là tìm đường đi dài nhất, ở đây nếu làm đúng mh sẽ ra được 2 đường có cùng giá trị lớn nhất này (bằng 9, cậu cộng cost các cạnh theo mỗi đường sẽ thấy), nhưng cách viết hiện tại trong hàm go() là chưa thích hợp, nhưng mh chưa biết sửa sao?!? Nên cậu có thấy cái if 1 loạt chấm hỏi chưa xử lý ko? Cái đó ban đầu mh định xử lý nếu 2 giá trị từ 2 đường đi tới đều = 9 thì xử lý sao đó...?

Cậu cho mình cái email nhe!
 

dt2it153

Member
14/7/11
92
2
8
nhà tui ^^
Khơi lại vấn đề cũ. Mình vẫn kẹt không biết lưu nhiều đường đi như thế nào trong quá trình chạy thuật toán Dijkstra trong hàm go() ở trên.
Mình nghĩ thêm cái if(newPossiblePathCost == adjNode.getDistance()) trong hàm go() để nó xử lý trường hợp khi cái adjNode là v5 như trong hình http://www.mediafire.com/view/?87g32yc3cr73wf4 mà trước đó đã có lưu v5.previous = v3, thì giờ nó xét tới đỉnh v4, biết v5 có previous là v4 mà cost của đường này (v1 - v2 - v4 - v5) = với cost của đường trước đó mà v5 ghi nhận (v1 - v3 - v5) = 9, thì nó lưu thêm cái previous của v5 nữa là v4. Đây là trường hợp 2 đường có cost = nhau.
Nhưng trong thân của cái if(newPossiblePathCost == adjNode.getDistance()) này mình ko biết code gì?
Nếu dùng biến previous thì không hợp lý vì nó sẽ ghi đè và chỉ biết dc có 1 đường thôi.
Vậy giờ mình dùng cấu trúc lưu gì đây để nó lưu dc 2 đường?
Mong mọi người xem xét giúp.