dpigeon / heuristic-indonesian-puzzle Goto Github PK
View Code? Open in Web Editor NEWFinds the optimal solution path with DFS, BFS and A* Algorithm in an indonesian dot puzzle.
Finds the optimal solution path with DFS, BFS and A* Algorithm in an indonesian dot puzzle.
As a user, I want to create an A* algorithm so that it find the optimal solution path.
As a user, I want to build an A* algorithm from inputs given to give us the proper searched nodes and solution path. The algorithm must follow f(n) = g(n) + h(n) where
In summary, it will have to keep track of the depth (g) and the estimate (h). The smaller f(n) will be chosen each iteration. The heuristic h will have to be ran on all nodes to evaluate their estimate.
Criteria of Acceptance:
As a user,
I want to be able to see the last move step when the solution path reaches the goal state.
Acceptance Criteria:
As a user, I want to create a Best First Search algorithm so that it find the solution path.
As a user, I want to build a Best First Search algorithm from inputs given to give us the proper searched nodes and solution path. The algorithm must follow f(n) = h(n) where g(n) is 0.
In summary, it will have to keep of the estimate (h) only. The smaller f(n) will be chosen each iteration. The heuristic h will have to be ran on all nodes to evaluate their estimate.
Criteria of Acceptance:
As a user,
I want to be able to see the board flip the 0 --> 1 and 1 --> of the surrounding of the tiled touches (up and down, not diagonally).
Acceptance Criteria:
As a user,
I want to optimize the DFS algorithm so that it is faster than it is right now.
As a user,
I want the algorithm A* and BFS to backtrack our heapQueue by looking at parents of the nodes so that we can put them perfectly in our closed list.
Acceptance of Criteria:
As a user,
I want to be able to read the whole file and create a list of board
Acceptance Criteria:
As a user,
I want to design a heuristic so that I can search and find the fastest possible path within the board. We should at least have 3 heuristics so that we can test them.
Acceptance Criteria:
As a user,
I want to have a base code that all the developers can work and begin with.
Acceptance Criteria:
As a user,
I want to be able to virtually create a tree of boards (nodes) to store the actions and nodes. Also, an open and closed list must be generated with a goal state function.
Acceptance Criteria:
As a user,
I want to be able to create and write the search output of a board for DFS.
Display the search path (list of nodes that have been searched).
f(n) g(n) h(n) 111101100
Acceptance Criteria:
As a user, I want to be able to transform the values of the token touched to the actual board token coordinates.
As a developer, I want obtained what token was pressed in order to see the solution path better in the output here #5.
Acceptance Criteria:
As a user,
I want to generate a BFS tree that will be based of A* so that it derives of it.
If a solution is found after searching <= max l nodes, your program will display the solution
using the same format as indicated above.
f(n) = 0 + h(n)
where g(n) = 0
Acceptance of Criteria:
As a user,
I want to generate an A* algorithm so that it traverses the whole program.
If a solution is found after searching <= max l nodes, your program will display the solution
using the same format as indicated above.
f(n) = g(n) + h(n)
Using a priority queue as an open list, we can either use the queue.PriorityQueue with best case O(n) and worst case O(n^2) compexity or the heapq which tends to be better and faster.
Acceptance of Criteria:
As a user,
I am unable to input any board I want. Indeed, 0's cannot be put in front of the value column in the input file. For example:
If n = 3 with values = 001010101
would not work since our parser would only see 1010101
and disregard the two first 0's.
Acceptance Criteria:
As a user,
I want to be able to see the time taken to go through the DFS algorithm so that I have a better understanding of it.
As a developer, I want to see how well some inputs can perform with time better than the others. This will be very useful for examples in the report.
Acceptance Criteria:
As a user, I want to optimize the last algorithms we have implemented so that we are sure that they deliver the real optimal solution.
As a user, I want to compare each estimate in the heap queue and see if there is a smaller estimate in the open or closed list. If there is, we must update the list by getting the node, removing it and adding the new low estimate node in the heap queue. Don't forget that heapify must be used each time we delete a node in the list so that we keep the order of the heap.
Acceptance of Criteria:
As a user,
I want to write a report of 4-5 pages with the information written in the requirements.
Project 1: Final Report
As a user,
I want to be able to create and write the solution output of a board for DFS.
If found within max_d levels, I want the program to display the initial configuration preceded by 0 and then show each move solutions with A1 0 1 1 1 1 1
after.
If no solution after searching > max_l nodes, then no solution
.
Acceptance Criteria:
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.