A Star Algorithm with UI

YongxiangJ — Thu, 25 Aug 2022 20:52:52 +0000

What is A Star Algorithm?

A* algorithm is a search algorithm usually used in path finding. It guarantees to find a complete and optimal path if there is one (the target is not surrounded by walls on all sides). Since it is an informed search, we have the control over where the target is and the distance between each nodes.

Why did I do it?

A* algorithm is one of the most frequent algorithms that I used during my undergraduate study. The map system for the hospital app, robot which explores the maze, and other projects all uses A* for path finding. Since I lost access to most of the project code, I would really like to rewrite the algorithm. I could also use this algorithm in the future projects if needed.

How did I do it?

I first implemented A* on nodes connected with edges. This was represented using a graph. I used priority queue for the algorithm because this data structure perfectly blends with A*'s property(v.0.1.0 release on GitHub).

Part 2

A* is cool in action. I decided to visualize the A* using a simple interactive UI. The Swing library was my first UI library, it's enough for a simple UI to use.

The Program

(The start of the program.)

(When we click on the Manual A* button, it proceeds with 1 step of A* search.)

(This is A* auto mode. This finds the path with 1 click.)

Time & Space Complexity

Time Complexity

In the worst case scenario, the time complexity is O(b^d), where b is the branching factor, and d is the depth of the solution. The branching factor is how many nodes we are comparing in an iteration. The depth is the the minimum number of nodes we need to take to reach the target(shortest path). The time complexity is exponential, because each node has 4 (or 8 if including diagonal nodes) neighbors to expand.

Space Complexity

The space complexity is the same as Time Complexity; O(b^d).

Tea Shop Recommendation System

YongxiangJ — Mon, 22 Aug 2022 00:09:46 +0000

What is it?

This program is used to return a list of possible items based on the user's input string.

Why?

I really like Chinese tea just as my father. He owns a tea shop called Orijin Tea. I tried to use the official website and found out that the search results were not so accurate. I suddenly realized that I can improve the search functionality.

Brief Methodology

There are two major parts to this system: saving data and retrieving data. The raw data are stored in a 2d python list. I put this data set into a hash table before running through the algorithm. To retrieve the correct product, I take the user input and go through each product. If the user input appears inside the product, then we can print that product for the user (in a specific format).

Current Progress

Right now, the program can quickly handle the whole tea collection at Orijin Tea (approximately 135 types of Chinese Tea). As the user types in a search text, the program suggests a few possible products, including the rating, price, tea origin, and its name.

(The ratings section is not set yet.)

The current data retrieval is good enough for small data. I tested it with 20k sized data set (20k tea data) and the time it iterated through the whole data set was approx. 0.04s.

Next Steps

I am considering to implement this functionality into GUI to visualize it better. Function wise, I am still trying to implement a better algorithm which can handle larger data sets.

If you want to see more details in code, follow on GitHub:
Link

Thank you for reading it through! ^_^

DEV Community: YongxiangJ