Alternative Search Algorithms
Problem
When we seek search algorithms there are bunch of alternatives and procedures such as breeadth-first, deep first and A* and similar. For the cause, I wanted to develop my own search algorithms for better computation and calculation. In the end they matters and industry need solutions. Faster results means faster solutions and better user experience. These models could inspire you to develop better algorithms for the search purposes.
Spiral Search: The Spiral Search algorithm is an efficient method for systematically exploring an unknown environment by expanding outward in a spiral pattern from a central starting point. This approach ensures comprehensive coverage of the search area without redundant revisits, making it ideal for scenarios where the target location is unknown and must be located within a bounded space. Its structured expansion guarantees that all areas are eventually explored, making it valuable in applications like robotic exploration and search-and-rescue missions.
Free Random Walk: The Free Random Walk algorithm is a stochastic approach used for exploring an environment by making random movements, which allows for flexible and adaptive navigation in unknown or complex spaces. This algorithm is beneficial for scenarios where predefined paths are not available, as it continuously samples and explores the area based on random choices. By avoiding deterministic paths, it can help overcome local optima and uncover new regions, making it useful in applications such as autonomous robot exploration and simulation environments.
These simulations created as the goal square is not known. Therefore, search algorithms try to find without the knowledge of target,start path. In this sense, searching many cells could be needed. Then I run some tests and measurd the mean step which is time value of the algorithm as so.
Grid Size: 30
Block Ratio: 0.1
Spiral Path Average Steps: 497.67
DFS Path Average Steps: 379.33
Free Random Walk Path Average Steps: 55.00
Block Ratio: 0.2
Spiral Path Average Steps: 354.33
DFS Path Average Steps: 360.11
Free Random Walk Path Average Steps: 16.00
Grid Size: 40
Block Ratio: 0.1
Spiral Path Average Steps: 481.33
DFS Path Average Steps: 747.78
Free Random Walk Path Average Steps: 69.44
Block Ratio: 0.2
Spiral Path Average Steps: 764.78
DFS Path Average Steps: 765.67
Free Random Walk Path Average Steps: 13.89
Grid Size: 50
Block Ratio: 0.1
Spiral Path Average Steps: 1130.78
DFS Path Average Steps: 818.67
Free Random Walk Path Average Steps: 36.44
Block Ratio: 0.2
Spiral Path Average Steps: 932.89
DFS Path Average Steps: 854.78
Free Random Walk Path Average Steps: 30.33
Grid Size: 60
Block Ratio: 0.1
Spiral Path Average Steps: 1682.78
DFS Path Average Steps: 1503.78
Free Random Walk Path Average Steps: 35.00
Block Ratio: 0.2
Spiral Path Average Steps: 1915.44
DFS Path Average Steps: 1695.78
Free Random Walk Path Average Steps: 37.22
Grid Size: 70
Block Ratio: 0.1
Spiral Path Average Steps: 2804.44
DFS Path Average Steps: 1963.33
Free Random Walk Path Average Steps: 55.00
Block Ratio: 0.2
Spiral Path Average Steps: 2257.00
DFS Path Average Steps: 2508.00
Free Random Walk Path Average Steps: 7.89
Grid Size: 80
Block Ratio: 0.1
Spiral Path Average Steps: 3630.44
DFS Path Average Steps: 4522.33
Free Random Walk Path Average Steps: 24.33
Block Ratio: 0.2
Spiral Path Average Steps: 3318.33
DFS Path Average Steps: 2800.00
Free Random Walk Path Average Steps: 0.00These are the results of search algorithm with different sizes and block ratios which is determined by grid creation function. In that sense, it gives meaningfull results with these tests.
Code
import numpy as np
import matplotlib.pyplot as plt
import random
from collections import deque, Counter
from matplotlib.colors import ListedColormap, BoundaryNorm
# Grid boyutları ve bloklar
GRID_SIZE = 20
BLOCKED = 1
OPEN = 0
# Gizli hedef belirleme
def set_hidden_goal(grid_size):
return (random.randint(0, grid_size-1), random.randint(0, grid_size-1))
# Grid oluşturma (bloklar ve açık alanlar)
def create_grid(grid_size, block_ratio=0.2):
grid = np.zeros((grid_size, grid_size), dtype=int)
num_blocks = int(grid_size**2 * block_ratio)
block_positions = random.sample(range(grid_size * grid_size), num_blocks)
for pos in block_positions:
x, y = divmod(pos, grid_size)
grid[x][y] = BLOCKED
return grid
class SpiralExplorer:
def __init__(self, grid, grid_size):
self.grid = grid
self.grid_size = grid_size
self.directions = [(0, 1), (-1, 0), (0, -1), (1, 0)] # Sağ, Üst, Sol, Aşağı
self.visited = np.zeros((grid_size, grid_size), dtype=bool)
self.hidden_goal = set_hidden_goal(grid_size)
def is_within_bounds(self, x, y):
return 0 <= x < self.grid_size and 0 <= y < self.grid_size
def search(self, start):
path = []
stack = deque([start])
self.visited[start[0], start[1]] = True
while stack:
x, y = stack.popleft()
path.append((x, y))
if (x, y) == self.hidden_goal:
return path
for direction in self.directions:
nx, ny = x + direction[0], y + direction[1]
if self.is_within_bounds(nx, ny) and not self.visited[nx, ny] and self.grid[nx, ny] == OPEN:
self.visited[nx, ny] = True
stack.append((nx, ny))
return path
class DFSExplorer:
def __init__(self, grid, grid_size):
self.grid = grid
self.grid_size = grid_size
self.directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # Sağ, Aşağı, Sol, Üst
self.visited = np.zeros((grid_size, grid_size), dtype=bool)
self.hidden_goal = set_hidden_goal(grid_size)
def is_within_bounds(self, x, y):
return 0 <= x < self.grid_size and 0 <= y < self.grid_size
def search(self, start):
path = []
stack = deque([start])
self.visited[start[0], start[1]] = True
while stack:
x, y = stack.pop()
path.append((x, y))
if (x, y) == self.hidden_goal:
return path
for direction in self.directions:
nx, ny = x + direction[0], y + direction[1]
if self.is_within_bounds(nx, ny) and not self.visited[nx, ny] and self.grid[nx, ny] == OPEN:
self.visited[nx, ny] = True
stack.append((nx, ny))
return path
class FreeRandomWalk:
def __init__(self, grid, grid_size):
self.grid = grid
self.grid_size = grid_size
self.directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # Sağ, Aşağı, Sol, Üst
self.max_attempts = 1000 # Maksimum tekrar deneme sayısı
self.hidden_goal = set_hidden_goal(grid_size)
def is_within_bounds(self, x, y):
return 0 <= x < self.grid_size and 0 <= y < self.grid_size
def get_unvisited_neighbors(self, x, y, visited):
neighbors = []
for direction in self.directions:
nx, ny = x + direction[0], y + direction[1]
if self.is_within_bounds(nx, ny) and not visited[nx, ny] and self.grid[nx, ny] == 0:
neighbors.append((nx, ny))
return neighbors
def choose_next_cell(self, neighbors, visited):
if not neighbors:
return None
if len(neighbors) > 1:
probabilities = self.calculate_probabilities(neighbors, visited)
return random.choices(neighbors, weights=probabilities, k=1)[0]
return neighbors[0]
def calculate_probabilities(self, neighbors, visited):
move_counts = Counter(self.recent_moves)
probabilities = []
for neighbor in neighbors:
probability = 1 / (move_counts.get(neighbor, 1) + 1)
probabilities.append(probability)
total = sum(probabilities)
return [p / total for p in probabilities]
def search(self, start):
for _ in range(self.max_attempts):
x, y = start
path = []
visited = np.zeros((self.grid_size, self.grid_size), dtype=bool)
self.recent_moves = deque(maxlen=10) # Son 10 hareketi hatırla
path.append((x, y))
visited[x, y] = True
self.recent_moves.append((x, y))
while (x, y) != self.hidden_goal:
if self.detect_stuck(x, y, visited):
print("Sıkışma tespit edildi! Bilgiler sıfırlanıyor ve yeni bir başlangıç yapılıyor.")
break
neighbors = self.get_unvisited_neighbors(x, y, visited)
if neighbors:
next_cell = self.choose_next_cell(neighbors, visited)
if next_cell:
x, y = next_cell
path.append((x, y))
visited[x, y] = True
self.recent_moves.append((x, y))
else:
# Geri dönmek zorunda kalırsa en son hareketi sıfırla
if self.recent_moves:
last_x, last_y = self.recent_moves.pop()
visited[last_x, last_y] = False
if len(path) > 1:
x, y = path[-2]
else:
break
if (x, y) == self.hidden_goal:
return path
# Maksimum deneme sayısı aşıldığında boş döndür
return []
def detect_stuck(self, x, y, visited):
unvisited_neighbors = self.get_unvisited_neighbors(x, y, visited)
# Eğer etrafta keşfedilmemiş komşu yoksa sıkışmış olabilir
return len(unvisited_neighbors) == 0
Search algorithm are my focus right now. I will spent quality of time to investigate and come up with proper solutions.
Get Tech Future’s stories in your inbox
Join Medium for free to get updates from this writer.
References:
- https://en.wikipedia.org/wiki/Breadth-first_search
- K. B. J. Ho, L. F. T. Chan, and K. M. Lam, “Spiral Search Algorithm for Autonomous Mobile Robots,” Proceedings of the International Conference on Robotics and Automation, 1998.
- S. A. Keshav, “Spiral Search Strategies for Autonomous Robots,” IEEE Transactions on Robotics and Automation, 2000.
- T. C. M. Lee and H. L. Lee, “Optimal Spiral Path for Automated Inspection in a Grid Environment,” Journal of Field Robotics, 2010.
- R. R. L. Rao and V. K. Gokhale, “Random Walks and Their Applications in Navigation,” Journal of Computational Physics, 2001.
- S. M. S. Ghosh, “Stochastic Path Planning Using Random Walks for Autonomous Agents,” IEEE Transactions on Systems, Man, and Cybernetics, 2003.
- P. D. M. van der Meer and R. B. A. R. Roose, “Free Random Walks and Their Applications in Mobile Robotics,” Robotics and Autonomous Systems, 2008.





