Hybrid Integrated Computing Algorithm for Sustainable Tourism

Abstract

To avoid destroying the natural environment, we can create tourist paths without disrupting ecological systems or rare places such as rainforests that contain endangered species. Likewise, in sustainable tourism, we should consider visiting national parks or national museums as a way to understand the core values and the meaning of that culture and environment more clearly. In this paper, we consider which points tourists need to avoid or visit for sustainable tourism. We designed an algorithm that can give a path to avoid certain points or to go to a preferred point. If this algorithm does not give any weight, it will give the shortest path from the start to the end, and it can decide which vertices to avoid or travel to. Moreover, it can be used to vary the weights of different positive or negative values to obtain a path to avoid a point or to reach a point. Compared to Dijkstra’s algorithm, we can add a negative weight to the graph and still find the shortest path. In application, it can be used for path schedule decisions. We did not wave the large resources to calculate the walk length. In the usage scenario, users only need to provide the starting node, end node, avoidance point, and facing point to calculate the best path. This algorithm will give a good path for users. At the same time, users can use this algorithm to implement sustainable travel route planning, such as going to museums, avoiding rare environments, etc. So, this algorithm provides a new way to decide the best path. Finally, the experimental results show that the classic algorithms cannot avoid points. In real tourism, tourists can use this algorithm for travel planning to achieve sustainable tourism.

1. Introduction

Human tourism activities and ecological conservation are often in conflict, as tourism causes destruction and disturbance to the ecosystem. Transportation is an essential source of carbon emissions [1]. High levels of carbon dioxide (CO₂) have destroyed animal habitats and interfered with plant and animal survival, reproduction, and migration environments [2,3]. Automobile accidents have also threatened many animals [4]. In Europe, every year thousands of mammals die on the roads [5]. More than 35,000 wildlife-vehicle collisions occur in the U.S. each year [6]. The United Nations warned in 2019 that human damage to the ecosystem is reaching severe proportions [7]. The balance between human tourism and ecological protection is a critical issue. Proper tourism paths should minimize the impact on the ecosystem and have a positive impact on the social and economic conditions [8,9]. Sustainable development (SD) is defined as satisfying people’s present needs without damaging future development needs. In the case of sustainable tourism, our research is focused on the protection of natural environmental resources via the planning of paths. In order to avoid damaging the natural environment, our travel routes bypass animal migration routes or rare animal habitats, reducing ecological damage while visiting a World Heritage Site or Ecological Reserve [9,10]. The research in this paper will help travelers achieve the coexistence of eco-experience and environmental protection while planning their travel paths. In addition, some travel destinations offer travel service that lack trust, lack security support, and have a high vulnerability to fraud [11]. To increase the safety of traveling, we can avoid these places while planning our trip. Every country’s tourism industry is expected to attract more tourists [6]. However, an excessive number of travelers will often cause ecological damage. Urban ecosystems combine topography, geomorphology, soil, climate, hydrology, plants, and animals. They are closely related to human activities. They are not only affected by human activities but also necessary for coexistence with humans [7] in order to sustain tourism activities, increase travel safety, and reduce ecological damage. With a sustainable travel perspective, we support better access points for the travel map and determine the best paths for the two access points (start and end). We designed an algorithm to develop better travel routes, avoiding unsuitable sites or sites that need to be protected and choosing routes that are more suitable for sustainable travel.

For sustainability, we designed a new algorithm called the hybrid integrated computing algorithm. In this study, we call it the HIC algorithm. It is based on Dijkstra’s algorithm and has three functions: avoidance points, preference points, and finding the shortest path in the graph. The time complexity of the HIC algorithm is O(V)², and we prove these functions in this paper.

The standard way to weight a graph has two solutions: weighted on the edge or vertices. In the single search shortest problem [8], for example, the Fibonacci heap [9] considers the number of edges. In the graph data structure, a vertex can add many edges without limit, but the number of edges cannot be more significant than the number of vertices. So, the HIC algorithm is very suitable in graphs, having small count vertices and large amounts of edges.

The path-finding topic typically consists of lots of the grid system, which means that every direction of movement has been designed [12,13]. In the graph data structure, we must consider whether the vertex’s connection with another vertex with the edge exists. Grid systems require many resources to compute and save to a cache for each matrix, e.g., 2D or 3D. We can use a grid system to demonstrate the pass structure or not as the adjacency.

This paper provides a high-order hybrid computational graph weighting method; it can be used for positive or negative weights in the HIC algorithm. For negative weights, path planning will treat these vertices as better approaches; the system will tend to add these vertices to the path. For positive weights, the planning system will avoid planning these positively weighted nodes as part of the path. This uses weighted changes in the neighborhood as new factors to select the following vertices. The primary technical support is divergence. We first consider the changes in the neighborhood and then calculate the flux of each node. When the flux is more significant than zero, selecting this point will increase the path’s cost. If the flux is less than zero, surrounding the path will release the cost in the path.

The HIC algorithm can significantly impact the Department of Sustainable Tourism. In sustainable tourism, we consider tourism of local culture and natural environment. Using positive weight can avoid local sanctuaries and the destruction of traditional aboriginal culture. In the natural environment, environmentally conscious tourists are willing to do their best to minimize their environmental impacts, such as reducing pollution, waste, energy consumption, water use, environmental chemicals, and unnecessary nighttime lighting. The HIC algorithm can help path planning be more environmentally conscious. For example, it adds the preferred environmental plane for tourists as negatively weighted and adds the unsustainable plane as positive to avoid this plane.

2. Literature Review and Background

In sustainable tourism worldwide, SDGs aim to educate, empower, and inspire tourism industry stakeholders to take necessary actions. They are aligned with global goals to achieve more sustainable tourism by transforming policies and business operations [14]. In this section, we will discuss the topic of sustainable tourism. It includes implementation aspects, core values, and challenges. We will explain how the HIC algorithm can be applied to sustainable tourism. We will also review the classical path-planning algorithms used in this study.

2.1. Differences between Sustainable, Ecotourism, Mass, and Conventional Tourism

Ecotourism involves the consideration of the environment, ecosystems, and wildlife [15]. Mass tourism involves the primary goal of making money for tourism service providers, and the primary goals of experiencing, entertaining, and satisfying the individual needs/wants of tourists paying for the service [16]. Traditional tourism may include mass tourism but also non-mass tourism in the form of traditional tourism and specialized tourism [17]. Sustainable tourism considers the economic, social, and environmental impacts of tourism in the short and long term for all tourism stakeholders [18].

2.2. How Can Tourism Be Made More Sustainable?

Tourism can be made more sustainable via several achievable measures. With technological solutions, we can quickly realize the sustainable development of tourism [19]. Others highlight conscious consumerism and ideas like slow travel [20]. However, with a growing population and endless consumer demand pitted against a fragile environment, we need a more concerted effort.

We can analyze how to make tourism more sustainable under different scenarios. On the government side, they must implement policies that foster sustainable development by overcoming the growth fetish. Tourism should be developed only within sustainable development parameters. The government must tackle the environmental limits to growth and climate change challenges. Therefore, we need the government tourism department to focus on integrated planning as much as they currently emphasize marketing.

Consumers should be educated on responsible travel choices. For example, few realize that all-inclusive resorts result in economic benefits from tourism leaking out of the host economy back to the home economies of the big multinationals and corporations that often own such resorts. Civic education in schools could teach responsible travel.

2.3. The Challenge of Sustainable Tourism

For sustainable development, rare animals and the environment should be protected. When tourism chooses the habitats of rare animals or precious natural environments as part of its agenda, it causes damage to the environment, which is not conducive to sustainable development. Almost every aspect of energy consumption to run a hotel or motel requires electricity and energy. From the gym to the kitchen and guest rooms, hotels use much energy to ensure that guests are comfortable. However, high energy consumption levels can quickly raise the travel carbon footprint and compromise sustainability efforts [21].

High energy consumption also means receiving more power-related bills. Not only does this erode hotels’ profits, but it also puts businesses in trouble with the law. For example, most governments have installed laws and policies to help cut down emissions and match the UN’s target of reaching net zero carbon emissions by 2050. As a result, business may be penalized or have its license revoked for failure to comply with these policies.

2.4. Improvements in Sustainable Tourism

Our global innovation ecosystem now includes over 12,000 start-ups from 160 countries, employing 83 million people and 300 corporate partners working on new tourism technologies. UNWTO’s education programs reached an unprecedented number of people, welcoming more than 20,000 students from 100 countries in 18 months. We promote lifelong learning thanks to partnerships with five world-leading organizations in tourism and hospitality.

2.5. Application

Many of us are turning to environmentally friendly choices in our daily lives [22,23], and we can adopt the same attitude when we are on the road and help ensure that oceans and other habitats reduce plastic waste: ditch single-use plastics. Tour operations involve many people, logistics, suppliers, transportation, and ethical operators [20]. In the meantime, we could even stop locally when eating. Buying local helps improve the local economy, which benefits local communities [24] and helps reduce the carbon footprint of goods transported to their destination.

There are many things to consider when we think about being unable to feed wildlife. When animals grow used to eating human food, their natural behavior changes to depend on humans. The struggle for survival can even lead to human–animal conflicts in some cases.

Tourism is developed and maintained to keep our beautiful environment alive indefinitely. In addition, we can also use public transportation to visit various attractions. Likewise, trains and taxis can both go. Before traveling, we should first understand the destination. Doing so will allow you to gain a deeper understanding of local traditions and customs and appreciate things you might not otherwise notice. Creating existing trails will help to understand the local culture, protect species and landscapes, and preserve these natural spaces for future visitors. At the same time, users can choose goods of the local culture to increase local economic growth.

2.6. Algorithms

In mathematics and computer science, algorithms are a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform computation [25]. In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

2.6.1. Dijkstra’s Algorithm

The process of Dijkstra’s algorithm is to keep track of the local best solution as the visit point when we do not know the shortest distance from each node to the source node nor can we find the shortest path. Dijkstra’s algorithm only works with graphs that have positive weights [26].

2.6.2. A Star

A star is an informed search algorithm, or best-first search, which means that it is formulated in the context of a weighted graph: starting from a specific starting node of the graph, it aims to find a path to a target node with the smallest cost. It does this by maintaining a tree of paths originating at the start node and extending those paths one edge at a time until its termination criterion is satisfied [27].

2.6.3. Best First

If we consider a search in a graph as traversal, an uninformed search algorithm will blindly traverse to the next node without considering the costs associated with that step. In contrast, informed search, such as BFS, will use an evaluation function to decide which node is the most promising among the various available nodes before traveling to that node [28].

2.6.4. Bi-Directional Search

Instead of searching from start to finish, you can start two searches in parallel, one from start to finish to start. When they meet, you should have a good path. It is a good idea that will help in some situations. The idea behind bidirectional searches is that searching results in a tree that fans out over the map. A big tree is much worse than two small trees. So, it is better to have two small search trees [29].

2.6.5. Breadth-First Search

Starting from the root, all the nodes at a particular level are visited first, and then, the nodes of the next level are traversed until all nodes are visited. To carry this out, a queue is used. All the adjacent unvisited nodes of the current level are pushed into the queue, and the nodes of the current level are marked as visited and popped from the queue [30].

2.6.6. Iterative Deep Depth-First Search

IDDFS combines depth-preferred search space efficiency with breadth-preferred search exhaustiveness. If a solution exists, it will find a path with fewer arcs. Since deep visits are repeated many times, this may seem wasteful. It may not be costly. Since most of the nodes in the tree are at lower levels. So, it does not matter if the upper level is visited more often.

The main advantage of IDDFS over the game tree search is that the previous search improves commonly used heuristics, such as the killer heuristic and alpha–beta pruning, so that the estimated scores of various nodes in the final depth search can be more accurate, and the search is completed more quickly because it is performed in a better order. For example, alpha–beta pruning is most effective if it first finds the best move [31].

2.6.7. Minimum Spanning Tree

A Minimum Spanning Tree (MST) is the subset of edges of a graph connected with edge weight and minimum possible total edge weight connecting all vertices without any cycles. This is a way to find the most economical way to connect a set of nodes. Minimum spanning trees are not necessarily unique. All edges in a graph have the exact weights, so every spanning tree in the graph is an MST. The edges of a minimum spanning tree can be found using greedy algorithms or more sophisticated Kruskal or Prim algorithms [32].

3. Materials and Methods

In this paper, the path-finding algorithm is improved to a new function. The function can find the best path in the map by selecting vertices to avoid points or to obtain selected points. To accomplish this goal, we use the Laplacian operator to help us design these functions. In addition, this research uses graph data structures as a background for designing algorithm experiments. We can save pixels for this using a manageable number of resources.

3.1. Gradient

The gradient (or gradient vector field) of a scalar function $f\left(x_1,x_2,\dots ,x_n\right)$ is denoted as $\nabla f$ or $\overrightarrow{\nabla }f$ where $\nabla$ (Nabla) denotes the vector differential operator, del. The notation gradf is also commonly used to represent the gradient. The gradient of f is defined as the unique vector field of which the dot product with any vector v at each point x is the directional derivative of f along V.

$$\left(\nabla f\left(x\right)\right)·v=D_{v}f\left(x\right)$$

(1)

where the right-hand side is the directional derivative, and there are many ways to represent it. Formally, the derivative is dual to the gradient. When a function also depends on a parameter such as time, the gradient often refers simply to the vector of its spatial derivatives only. The magnitude and direction of the gradient vector are independent of the particular coordinate representation.

3.1.1. Cartesian Coordinates

In the three-dimensional Cartesian coordinate system with a Euclidean, the gradient, if it exists, is given via

$$\nabla f=\frac{\partial f}{\partial x}i+\frac{\partial f}{\partial y}j+\frac{\partial f}{\partial z}k$$

(2)

where i, j, and k are the standard unit vectors in the directions of the x, y, and z coordinates.

3.1.2. General Coordinates

We consider general coordinates, written as x1, …, xi, …, xn, where n is the number of dimensions of the domain. The upper index refers to the position in the list of coordinates or components. So, x2 refers to the second component—not the quantity x squared. The index variable i refers to an arbitrary element xi. Using Einstein’s notation, the gradient can then be written as

$$\nabla f=\frac{\partial f}{\partial x^i}{g}^{ij}{e}_j$$

(3)

where ei = ∂x ∂xi and ei = dxi refer to the unnormalized local covariant and contravariant bases, respectively, gi j is the inverse metric tensor, and the Einstein summation convention implies summation over i and j.

3.2. Divergence

The divergence of the vector field $F\left(x\right)$ at the point $x_0$ is defined as the ratio limit of the surface integral F outside the closed surface of the volume $x_0$ enclosed by V, volume of V, because V shrinks to zero.

$$divF|x_0=\underset{\mathit{V}\to 0}{\lim }{∯}_{S\left(V\right)}^{}F·\widehat{n}dS$$

(4)

where V is the volume of V, S(V) is the boundary of V, and $\widehat{n}$ is the normal external unit of the surface. It can be shown that the upper bound always converges to the same value for any sequence of volumes at $x_0$ and approaching zero volume. The result, divF, is a scalar function of x.

Since this definition is coordinate independent, it implies that the deviation is the same in any coordinate system. Although it is not often used practically to calculate deviation; When a vector field is given in a coordinate system, it is convenient to use the coordinate definitions below.

A vector field with zero divergence everywhere is called a Solenoidal, in which case there is no net flux on any closed surface.

3.2.1. Cartesian Coordinates

If the divergence of the point is negative, it indicates that the point has a positive source of emitted flux. If the divergence of the point is positive, the point indicates a negative source of absorbed flux. If the divergence of the point is equal to zero, the point does not have any flux.

$$Div\left(\overrightarrow{F}\right)=\nabla ·\overrightarrow{F}=\left(\frac{\partial }{\partial x}+\frac{\partial }{\partial y}+\frac{\partial }{\partial k}\right)·\left(f_1+f_2+f_3\right)$$

(5)

At the same time, we can write the formula as follows:

$$\begin{array}{c}\mathrm{div}A=\underset{V\to 0}{\lim }\frac{{\iint }_{\partial V}A·dS}{{\iiint }_{V}dV}\\ =\frac{A_x\left(x+dx\right)dydz-A_x\left(x\right)dydz+A_y\left(y+dy\right)dxdz-A_y\left(y\right)dxdz+A_z\left(z+dz\right)dxdy-A_z\left(z\right)dxdy}{dxdydz}\end{array}$$

(6)

3.2.2. General Coordinates

Using Einstein’s notation, we can consider divergence in generalized coordinates, which we write as x1, …, xi, …, xn, where n is several domain dimensions. Here, the upper index refers to the number of coordinates or components, so x2 refers to the second component, and not the quantity x squared. The index variable i is used to refer to an arbitrary component, such as xi. The divergence can then be written via the Voss–Weyl formula:

$$div\left(F\right)=\frac{1}{\rho }\frac{\partial \left(\mathsf{\rho }{F}^i\right)}{\partial x^i}$$

(7)

where ρ is the local coefficient of the volume element, and Fi is the component F = Fi ei with respect to the unnormalized local covariance basis. Einstein’s notation implies a summation over i since it appears as an upper and lower index.

3.3. Laplacian Operator

The Laplace operator is a second-order different operator in the n-dimension Euclidean space, defined as the divergence ($\nabla$) of the gradient ($\nabla f$). Thus, if f is a twice-differentiable real-valued function, then the Laplacian of f is the real-valued function defined as follows:

$$\mathsf{\Delta }\left(f\right)={\nabla }^2\left(f\right)=\nabla ·\nabla f=div\left(gradf\right)$$

(8)

where the latter notations derive from formally writing

$$\nabla =\left(\frac{\partial }{\partial x_1},\dots ,\frac{\partial }{\partial x_n}\right)$$

(9)

Meanwhile, the Laplacian of f is thus the sum of all the unmixed second partial derivatives in the Cartesian coordinates x_i:

$$\mathsf{\Delta }f={\sum }_{i=1}^n\frac{{\partial }^{2}f}{\partial x_i^2}$$

(10)

As a second-order differential operator, the Laplace operator maps C^k functions for C^k−2 function for k ≥ 2. It is a linear operator Δ: C^k(Rⁿ) → C^k−2(Rⁿ), or more generally, an operator Δ: C^k(Ω) → C^k−2(Ω) for any open set Ω ⊆ Rⁿ.

3.4. Graph Matrix

Graph matrix is a data structure that can assist in developing a tool for automation of path testing. Properties of graph matrices are fundamental for developing a test tool and hence graph matrices are very useful in understanding software testing concepts and theory.

3.4.1. Adjacency Matrix

G:= (V, E) where V:= {v₁, v₂, …, v_n} is the set of nodes/vertices and E:= {e₁, e₂, …, e₃} is the set of the edges, with an adjacency matrix A ∈ {0, 1}^n×n

$$A_{ij}≔\left\{\begin{array}{lll}1& if& thereisanedgebetween{v}_{i}and{v}_j\\ 0& if& otherwise\end{array}\right.$$

(11)

3.4.2. Degree Matrix

The degree matrix D ∈ Z

$$D_{ij}≔\left\{\begin{array}{lll}degree\left(v_i\right)& if& i=j\\ 0& if& otherwise\end{array}\right.$$

(12)

3.4.3. Incident Matrix

In the incident matrix A, the row of A corresponds to the sorted vertices and the columns correspond to the sorted edges. For the vertex v_i and edge e_j:= (v_k, v_h), the entry K_i,j is defined as

$$A_{ij}≔\left\{\begin{array}{c}\begin{array}{c}\begin{array}{c}1ifi=kandi>h\\ 1ifi=handi>k\\ -1ifi=kandi<h\end{array}\\ -1ifi=handi<k\end{array}\\ 0ifothewise\end{array}\right.$$

(13)

3.4.4. Laplacian Matrix

Given a Graph G with n vertices v₁, …, v_n, the Laplacian matrix L_n×n is defined elementwise as

$$L_{ij}≔\left\{\begin{array}{c}degifi=j\\ -1ifi\ne jisadjencentto{v}_j\\ 0ifotherwise\end{array}\right.$$

(14)

4. HIC Algorithm

Our algorithm needs to compose the Laplacian operator and Laplacian matrix to add the weight onto the edge. Thus, we improve the original Dijkstra algorithm.

At first, we needed clarification on how to search the node and edge. The standard method is to transform the whole system into a cartesian coordinate system. For example, we can use a maze, the wall, and the path, which can change the walk to one and zero. One stands for the path, and zero stands for the wall.

In the experiment, we have an object that needs to compare the algorithm we use in the grid system. The grid system is based on the heuristic, and there are three types of moving models: Manhattan distance, diagonal distance, and Euclidean distance.

For the maze structure, we consider many walls to add the hard level. If the level is too low, all the degrees of distance will come to the same value, so, for this reason, we add many walls to challenge the power of the Algorithm.

So, for the grid system, we must consider two dimensions. First, we must prove the theorem of one dimension using the Taylor series. H stands for the most minor walk in the discrete function space, meaning that

$$\begin{array}{c}{x}_{i+1}-x_i=h\\ x_i-x_{i-1}=h\\ ⋮\end{array}$$

(15)

We must also use Taylor’s formula to compute the function value of f(x_i+1) and f(x_i−1) at the point x_i.

$$f\left(x_{i+1}\right)=f\left(x_i\right)+f^{\prime }\left(x_i\right)h+\frac{f^{″}{x}_i}{2!}{h}^2+\dots$$

(16)

$$f\left(x_{i-1}\right)=f\left(x_i\right){-f}^{\prime }\left(x_i\right)h+\frac{f^{″}{x}_i}{2!}{h}^2-\dots$$

(17)

For the minimum error range, we use (16) minus (17) to obtain

$$f^{\prime }\left(x_i\right)=\frac{f\left(x_i\right)-f\left(x_{i-1}\right)}{2h}-O\left(h^2\right)$$

(18)

So, the first derivative of the discrete function is

$$f^{\prime }\left(x_i\right)\approx \frac{f\left(x_i\right)-f\left(x_{i-1}\right)}{2h}$$

(19)

and the approximate error will be O(h²). We can use this to obtain f″(x_i) and add (1) and (2) to obtain

$$f^{″}\left(x_i\right)=\frac{f\left(x_{i+1}\right)-f\left(x_{i-1}\right)-2f\left(x_i\right)}{h^2}-O\left(h^3\right)$$

(20)

So, the second derivative in the discrete function is

$$f^{″}\left(x_i\right)\approx \frac{f\left(x_{i+1}\right)-f\left(x_{i-1}\right)-2f\left(x_i\right)}{h^2}$$

(21)

If we consider the four directions that the grid system can move, i.e., up, right, down, and left, that will be

$$\begin{array}{c}∆\mathrm{f}=\frac{{\partial }^2\mathrm{f}}{\partial {\mathrm{x}}^2}+\frac{{\partial }^2\mathrm{f}}{\partial {\mathrm{y}}^2}\\ =f\left(x+1,y\right)+f\left(x-1,y\right)-2f\left(x,y\right)+f\left(x,y+1\right)+f\left(x,y-1\right)-2f\left(x,y\right)\\ =f(x+1,y)+f(x-1,y)-2f(x,y)+f(x,y+1)+f(x,y-1)-\\ 2f(x,y)\end{array}$$

(22)

We have known from the above that the Laplace operator can calculate the gain of a point to a small perturbation on all its degrees of freedom. Then, through the graph, any node j changed to the node i brought about by the gain. We consider the graph of the edges of the weights of the same value using the following:

$$∆f={\sum }_{j\in N_i}{f}_i-f_j$$

(23)

if edge $E_{ij}$ have weight $w_{ij}$,

$$∆f={\sum }_{j\in N_i}{W}_{ij}{(f}_i-f_j)$$

(24)

and then

$$\begin{array}{cc}∆f& ={\displaystyle \sum _{j\in N}}{w}_{ij}(f_i-f_j)\\ & ={\displaystyle \sum _{j\in N}}{w}_{ij}{f}_i-{\displaystyle \sum _{j\in N}}{w}_{ij}{f}_j\\ & =d_i{f}_i-w_{i:}f\end{array}$$

(25)

and the $d_i=\sum _{j\in N}{w}_{ij}$ is the point i, $w_{i:}=\left(w_{i1,\dots ,W_{iN}}\right)$ is the column vector of N dimension, $f=\left(\begin{array}{c}∆f_1\\ ⋮\\ ∆f_N\end{array}\right)$ is the row vector of N dimension for all node N.

$$\begin{array}{cc}∆f_i& =\left(\begin{array}{c}∆f_1\\ ⋮\\ ∆f_N\end{array}\right)\\ & =\left(\begin{array}{c}{d}_1{f}_i-w_{1:}f\\ ⋮\\ d_N{f}_N-w_{N:}f\end{array}\right)\\ & =\left(\begin{array}{c}{d}_1{f}_i-w_{1:}f\\ ⋮\\ d_N{f}_N-w_{N:}f\end{array}\right)-\left(\begin{array}{c}{w}_{1:}\\ ⋮\\ w_{N:}\end{array}\right)\\ & =diag\left(d_i\right)f-W_f\\ & =(D-W)f\\ & =Lf\end{array}$$

(26)

4.1. HIC Algorithm Process

In design Algorithm 1, the HIC algorithm, this paper uses an incidence matrix to define the edge. This research considers the lower index as positive and the higher index as negative. It uses an adjacency matrix to ensure the node is connected to the nodes of the Laplacian matrix to calculate the divergence of the selection node. The weight is added to every node, and all weights are saved to the function matrix. The gradient matrix is defined as the incident matrix times the function matrix. The divergence matrix is defined as the Laplacian matrix times the function matrix. The graph transformed to a vertex-weighted graph, the weight is added to the vertices, and the n index vertex weighted is the n index divergence.

Algorithm 1 HIC Algorithm

1:   procedure HIC(Graph, source) 2:   for each vertex v in Graph.Vertices do 3:     dist[v] $\leftarrow$ INFINITY 4:     prev[v] $\leftarrow$ UNDEFINED 5:     add v to Q 6:    end for 7:    dist[source] $\leftarrow$ 0 8:    while Q is not empty do 9:     u $\leftarrow$ vertex in Q with min dist[u] 10:   remove u from Q 11:   for each neighbor v of u still in Q do 12:    alt $\leftarrow$ dist[u] + Graph.Vertices(u, v).weight 13:    if alt < dist[v] then 14:     dist[v] ← alt 15:     prev[v] ← u 16:    end if 17:   end for 18:  end while 19:  return dist[], prev[] 20: end procedure

4.2. Theorem for HIC Algorithm

Distance: The length of the path that supports from the HIC algorithm.

Path: The path from the start node and end node that result from the HIC algorithm.

Theorem 1.

The algorithm will tend to choose the most least divergence as the best selection.

Proof of Theorem 1.

The gradient is an operator that takes a multivariate function for input and produces a vector field. This paper uses weights as the function to be a baseline to input. The divergence from one point shows that the flux at any point in this vector field will correspond to the gradient of change in the steepness of f. We consider the meaning of three different types:

(1)

If divergence is bigger than zero, there is more flow coming out of the point than into the point.

(2)

If divergence is equal to zero, there is an equal amount of flow going into and out of the point.

(3)

If divergence is less than zero, there is more flow into the point than going away from the point.

This paper uses this thing to be the mind when the algorithm chooses which point is better. Likewise, the algorithm will choose the negative divergence to be the next point because when it chooses the most negative divergence, it can obtain the least lost in the search life cycle. □

Theorem 2.

When all weight values are the same value, the path will be the shortest path.

$$distance=minpath$$

Proof of Theorem 2.

When all weight values are the same value, every point’s gradient will be zero. Meanwhile, every point’s divergence will be zero, so the vertex-weighted graph will be transformation to unweighted graph and return to use Dijkstra’s algorithm to search the shortest path. □

Theorem 3.

HIC algorithm can choose the path which avoids one point and still can find the shortest path.

(1) 

If we consider it the shortest path problem, then just the positive is weighted.

(2) 

If the vertices are seen as positive weighted, and edge is gone, but no edge connects with the start node and end node; this situation will not be considered as our proof.

Theorem 4.

If we give a negative weight, the path will tend to choose this point as one of the vertices.

5. Experiment and Results

In order to examine the applicability and effectiveness of the HIC algorithm, we discuss it in four different types of scenarios. We take a series of steps to obtain detailed data to understand the algorithm’s performance.

5.1. The Iterative

In the problem of finding paths, it is usual to use mathematical methods. Algorithms for building least-cost paths are created by dealing with the properties of abstract graphs and by specifying and analyzing the nodes of an ordered checking graph. One of the most famous algorithms is Dijkstra’s algorithm. However, the math approach is usually more concerned with the final realization of the solution and rarely considers the time complexity of the algorithm.

This paper uses a grid system to demo the 100 × 100 mazes. The affection of classic algorithm had written in

Table 1. The different algorithm effect.

Algorithm Name	Iterative	Path Length
A Star	6822	242
Best First	295	242
Bi-direction	3300	272
Breadth First	23,798	245
Minimum Spanning Tree	23,978	242
Dijkstra’s	23,789	242
HIC	23,789	242

. In Table 1, we wrote the iterative of those algorithms to find the path from 374 the start node and end node. In more detail, we add a column describing the path length from those algorithms.

Figure 1 shows the 100 × 100 mazes as Section 5.1’s experiment background. Figure 2 shows the path from A star as an example.

In Figure 3 and Figure 4, the x-axis represents the length of the maze. In this experiment, the columns and rows of the maze have the same value. In other words, the maze is a cubic maze. The y-axis represents the amount of recursion. From Table 1, we can see that even though the mathematical approach has more computing resources than the heuristic approach. We can still find the connected paths. When the size of the computational graph is not large, we can know that the number of iterations of the mathematical approach and the heuristic approach are close to each other.

5.2. Heuristic and Mathematical Approach

The heuristics approach refers to a method of discovery based on rules of thumb. When a person solves a problem and selects methods that have worked well rather than a systematic, deterministic step-by-step search for an answer. In path-finding problems, using special knowledge about the domain of the problems represented by the graph. The heuristics can often improve the computational efficiency of the solution to a particular graph search problem. However, the heuristics are usually only guaranteed to find the solution path with the lowest cost. Figure 5 is the map of Tokyo that we picked up to demo. This map has 13 vertices and 27 edges. We picked up this location because we wanted a circle with a big loop on the outside. Figure 6 is a transformed figure as a graph data structure. In this experiment, we set the start node at index 1 and the end node to index 13. The red bar is the path, which is offered via algorithms.

Then, we demonstrate the grid system and graphical data structure. Figure 7 and Figure 8 are based on the grid system. Figure 9 is based on the graph data structure.

Figure 7 offers the path result via algorithms, including A*, Dijkstra, Bidirectional Search, Breadth First Search, Iterative Deep depth-first search, and Minimum Spanning Tree. Figure 8 is the search result via the Best First algorithm.

Figure 9 is based on the graph data structure and the results. As a result, we can know that graph data structures work better than grid systems.

In graph data structure, the edge takes the message that those vertices connect. However, in the grid system, when we make the same map that contains all connect relationship, the grid system will take every point as a walk distance. That will be a limit to designing the structure. Therefore, we use the graph data structure as our following experimental background.

5.3. Avoid or Not

After choosing the algorithm to be improved, we perform the comparison again. We consider two primary points: one is whether it avoids the selected point. The other is that this path under the satisfaction condition will not be too long. We can use a classic path- finding algorithm to check the smallest path. In this experiment, we set the start node at index 1 and the end node to index 13. The red bar is the path, which is offered via algorithms.

Figure 10 is the path created using the Dijkstra algorithm in the graph data structure. When the situation is that all vertices have the same weighted value, Figure 11 is the path created via the HIC algorithm in the graph data structure.

As a result, we can prove that Theorem 2 is when all weighted vertices have the same value. The HIC algorithm will turn to the Dijkstra algorithm.

Figure 12 represents the vertices with an index that is two, i.e., a positive weight. The divergence and gradient can be obtained by computing the function on the points. As a result, we found that HIC algorithm chooses the path to avoid the point at which the index is two. At the same time, the HIC algorithm can still find the shortest path. Therefore, we can prove that Theorem 3 is true.

Figure 13 and Figure 14 add a negative weight at vertices, with an index of 3. Furthermore, Figure 13 adds the positive weighted at the vertices of index 11. Figure 14 is adding the positive weighted at the vertices of index 12.

As a result, when we give a negative weight to the node, the path will take this point. We prove that Theorem 4 is true. In the same graph, we can add different positive and negative weight values. The paths will satisfy both avoidance and travel needs.

As shown in Figure 14, the path can either avoid index 3 or not avoid index 11. Thus, we can compare the two scenarios. The difference between the two graphs is that the HIC algorithm can handle the avoided index points.

5.4. Use Case in Real World

Section 5.3 shows the function of the HIC algorithm to avoid the point, perform the point, and find the shortest path when every weight has the same value. The experiments in this section demonstrate the HIC algorithm for real-world use. In order to validate real-world applications, we need to consider the connection status of the vertices. If the vertices are connectable, the edges can be of any shape. That is natural in the graph data structure. In the real world, the path should be following the real-world path. In this study, we adopted the geography of the United States and utilized it to experiment with paths and locations on a map. The red bar is the path, which is offered via algorithms.

Figure 15 is a real-world map of the United States in Phoenix. Figure 16 shows the vertices of this graph data structure. The index is organized in a top-to-bottom, left-to-right arrangement. The order is top, left, bottom, and right. In this experiment, the start node is index 1, and the end node is index 17. The starting vertex is at the top left, and the ending vertex is at the bottom right.

Figure 17 shows the result when index 13 is a positive weight. Figure 18 shows the result when index 2 is a negative weight. Figure 19 shows the result when index 5 is a positive weight. Index 4 is a negative. In Section 5.3, we know that those features give a negative weight that vertices will be the preferred node. Those features give a positive weight that point will be avoided and explored on the result. With this experiment, we can demonstrate the outcome of the real-world application.

This experiment uses real-world maps to design graphical data structures. The HIC algorithm was tested in three situations. The first type is the positively weighted single condition. The second is a negatively weighted single condition. The third type is multiple conditions combining positive and negative weighting. The results show that the proper paths were computed in all cases. Therefore, based on these results, we know that HIC algorithm can be applied to real-world maps.

This experiment uses real-world maps to design graphical data structures. The HIC algorithm was tested three situations. The first type is the positively weighted single condition. The second is a negatively weighted single condition. The third type is multiple conditions combining positive and negative weighting. The results show that the proper paths were computed in all cases. Therefore, based on these results, we know that HIC algorithm can be applied to real world maps.

6. Discussion

The weighting we have adopted is on the vertices, not on the edges. With this solution, we can reduce many resources by increasing the weight. If weighted on the edge, there will be a problem. A node can connect many edges. Our graph data structure has 13 nodes, but this structure has 27 edges. Therefore, using the vertices-weighted method, we can consider the weight.

The time complexity of the HIC algorithm is O(V²). The results of the experiment show that our time complexity is the same as Dijkstra’s algorithm, but the HIC has more features. The HIC algorithm can implement any of the features of Dijkstra’s algorithm. Dijkstra’s algorithm is based on the greedy algorithm, and the weights for weighting cannot be negative. In the HIC algorithm, negative weights (avoid) are allowed.

The HIC algorithm is a mathematical approach that has a higher time complexity compared to the heuristic approach. However, the probability of searching for the best path, avoiding points, and selecting points is outstanding.

The HIC algorithm is based on the general coordinate. It will not obtain the limit of Manhattan distance or Euclidean distance. Even if it has the same meaning as that point, it will consider every pivot chosen to obtain the correct answer.

When designing an itinerary, travelers need to consider many things, such as whether the paths are connected, how to add avoidance points and preference points, and so on. The HIC algorithm can select input data as a starting point, endpoint, avoidance point, and trend point. The HIC algorithm will then prioritize paths suitable for these situations. This design saves users the time of planning paths that do not meet their needs. We can apply sustainable tourism to reduce ecological damage. Travelers will maximize their efforts to protect the environment.

The HIC algorithm certainly has some limitations. The weight on any vertices only considers the actual number, and the HIC algorithm considers the positive and negative of the natural number system. Moreover, the number of edges is more significant than the number of vertices. In that case, the efficiencies will be lower than in another algorithm in which time complexity obtains edges, such as a map with a shallow number of edges and many vertices. This type of graph will be considered unsuitable for the HIC algorithm.

7. Conclusions

In this research, we conducted four experiments to verify the HIC algorithm in different situations. The experiments in Section 5.1 show that for a moderate number of maps, our proposed algorithm works correctly and with nearly the same efficiency. The experiments in Section 5.2 show that using a grid system demonstration produces a small error that can be avoided using our approach. Section 5.3 demonstrates the capabilities of the HIC algorithm on graph data structures. The experiments in Section 5.4 demonstrate the capabilities of the HIC algorithm on real-world maps. From these results, we can see that the application of HIC algorithm in path planning is promising. When using the map to search, in order to achieve sustainable tourism, we will consider many limitations.

Our method would avoid animal migration paths or areas with many rare animals to avoid ecological damage caused by carbon emissions or traffic accidents. We can use the HIC algorithm to decide which point we want to avoid and which point we want to use. Meanwhile, when we did not know which point to avoid and close in, the path would be the shortest from our start and end points. Those functions can all be implemented when using the HIC algorithm. The HIC algorithm allows travelers to set the place to go and the points to be avoided. If there is no particular point set to be avoided, it will select the shortest path for the user. If the given weight is negative, our algorithm will prefer to that point. The results of our experiments can demonstrate this.