pgr_bdastar doesn't return the same result as pgr_astar

Đang mở
  • Có gì không ổn?
#1,885 3 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 3 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
4/5
Thời gian dự kiến
3-5 ngày
Mức phù hợp với người mới
45/100
Loại issue
Lỗi
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Đình trệ
Công nghệ
postgresql
Lĩnh vực
backend, databases

Hướng nghiên cứu

The issue is in the pgRouting library's bidirectional A* algorithm (pgr_bdastar) returning a different path than the unidirectional A* (pgr_astar). Start by examining the test data in edge_min_repro.zip to understand the graph structure. Look at the source code for both algorithms, likely in src/astar/ or similar directories. Compare the heuristics and bidirectional search logic. Run the provided queries on the sample data to reproduce the discrepancy. 'Done' is when both algorithms return identical paths and aggregate costs for the given input.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

Documentation

Problem

pgr_bdastar doesn't return the same result as pgr_astar

To Reproduce

Using pgRouting docker image, import the following data:

edge_min_repro.zip

Then run the following queries:

SELECT 
seq, path_seq AS "pathSeq", node, edge, pgr.cost, agg_cost AS "aggCost"
FROM pgr_bdastar('SELECT * FROM edge', 1153548005, 558255664, true) as pgr
ORDER BY seq;

which returns:

1 1 1153548005 54256 0.000379723504336132 0
2 2 558255704 54146 0.000304523536838747 0.000379723504336132
3 3 558255705 54149 0.00138401927422877 0.00068424704117488
4 4 558255703 54142 0.000341445410931827 0.00206826631540365
5 5 558255702 54141 0.00148219733407846 0.00240971172633548
6 6 558255664 -1 0 0.00389190906041394

and

SELECT 
seq, path_seq AS "pathSeq", node, edge, pgr.cost, agg_cost AS "aggCost"
FROM pgr_astar('SELECT * FROM edge', 1153548005, 558255664, true) as pgr
ORDER BY seq;

which returns:

1 1 1153548005 54256 0.00037972350433613237 0
2 2 558255704 54147 0.00027403899672301315 0.00037972350433613237
3 3 1037080644 54145 0.0002883815801048997 0.0006537625010591456
4 4 1037086594 54144 0.0005431804623754474 0.0009421440811640453
5 5 1037074188 54143 0.0003132688487491818 0.0014853245435394926
6 6 558255702 54141 0.001482197334078463 0.0017985933922886744
7 7 558255664 -1 0 0.0032807907263671375

Expectation

Result should be the same, with the same sequence and the same aggCost.

Sample Data

Uploaded above.

Platform/versions

docker images 11-2.5-2.6.2 or 12-3.0-3.1.0 or 13-3.1-3.1.3

Ngôn ngữ chính
C++
Star
1.4k
Fork
397
Merge trung bình
2 ngày 16 giờ
Pull request đã merge (30 ngày)
8

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của pgRouting/pgrouting

Tất cả issue của pgRouting/pgrouting

Issue tương tự

Thêm issue về C++

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.