bề rộng-tìm kiếm đầu tiên trên biểu đồ lớn với ít ram

Question

Tôi hiện có biểu đồ có khoảng 10 triệu nút và 35 triệu cạnh. Hiện tại, đồ thị hoàn chỉnh được tải vào bộ nhớ khi bắt đầu chương trình. Điều này mất một vài phút (nó là Java sau khi tất cả) và cần khoảng một nửa gigabyte RAM. Hiện tại, nó chạy trên một máy tính với bộ xử lý lõi kép và 4 GB RAM.

Khi đồ thị được tìm kiếm bằng cách sử dụng tìm kiếm theo chiều rộng, mức sử dụng bộ nhớ tăng lên đến đỉnh một gigabyte và trung bình mất mười giây.

Tôi muốn triển khai chương trình trên một vài máy tính. Các chức năng ngoài việc tìm kiếm đồ thị có rất ít tài nguyên. Hệ thống đích của tôi rất nhỏ và chỉ có 512 megabyte RAM.

Bất kỳ đề xuất nào về cách triển khai phương thức (có thể sử dụng cơ sở dữ liệu) để tìm kiếm biểu đồ đó mà không tốn quá nhiều bộ nhớ? Chương trình hầu như không hoạt động vì nó đang truy cập thiết bị phần cứng, vì vậy việc tìm đường dẫn có thể mất khoảng 5 phút tối đa cho biểu đồ được đề cập ...

Cảm ơn mọi ý nghĩ đã được đưa ra.

CẬP NHẬT:

Chỉ tìm thấy neo4j. Có ai biết liệu nó có phù hợp với loại đồ thị khổng lồ này không?

Answer 1

Câu hỏi của bạn hơi mơ hồ, nhưng nói chung, một chiến lược tốt mà chủ yếu tuân theo ngữ nghĩa đầu tiên trong khi sử dụng cùng một lượng bộ nhớ như tìm kiếm theo chiều sâu là Iterative Deepening. Ý tưởng là bạn thực hiện tìm kiếm chiều sâu đầu tiên giới hạn ở mức 1 ở lần đầu tiên; nếu điều đó không tìm được giải pháp, hãy bắt đầu từ đầu và giới hạn nó thành 2 cấp độ; nếu điều đó không thành công, hãy thử 3 cấp độ, v.v. Điều này có vẻ hơi dư thừa lúc đầu, nhưng vì bạn đang thực hiện tìm kiếm theo chiều sâu, bạn giữ ít nút hơn nhiều trong bộ nhớ và luôn tìm kiếm một mức ít hơn một tìm kiếm đơn giản đầu tiên. Vì số lượng các nút trong một cấp phát triển theo cấp số nhân, trên các đồ thị lớn hơn, rất có khả năng là tiết kiệm được một mức bổ sung cuối cùng sẽ trả hết cho việc thử tất cả các lớp trước đó một cách dư thừa.

Answer 2

Tôi sẽ nói rằng Neo4j chắc chắn là một cách tốt để đi khi bạn có một đồ thị có kích thước khá như thế này. Nó không chỉ có các thuật toán BFS tích hợp mà bạn còn lưu giữ dữ liệu trên đĩa, do đó giảm thời gian khởi động của bạn.

Kiểm tra này ra trên highscalability.com: NEO4J - A GRAPH DATABASE THAT KICKS BUTTOX

Tôi đã sử dụng Neo4j và tài liệu của họ là rất tốt, và họ cung cấp một số nhận được ví dụ bắt đầu tốt đẹp, mà thực sự chỉ mất một vài phút để có được đi.

Check-out của họ - Getting started in 10 minutes guide

Answer 3

Neo4j lưu trữ dữ liệu trong cơ sở dữ liệu như đồ thị, nó trở nên khăng khăng và bạn có thể truy cập bằng cách sử dụng Graph Traversal Api (BFS, DBS, A * Dijkstra ...), hoặc Sử dụng truy vấn Cypher ngôn ngữ.