What is optimality principle?

A network consists of nodes which require communicating with other on various grounds. This communication is established via communication channels that exist between them. The communication involves data transfers. In a network a node may or may not have a link with every other node in the network. 

Applications that require communicating over a network include:

1. Telecommunication network applications such as POTS/ PSTN, local area networks (LANs), internet, mobile phone networks and so on.

2. Distributed system applications

3. Parallel system applications

- As we mentioned above, each and every node might not be linked with every other nodes since for doing so a lot of wires and cables are required which will the whole network more complicated. 

- Therefore, we bring in the concept of the intermediate nodes. 

- The data transmitted by the source node is forwarded to the destination by these intermediate nodes. 

Now the problem that arises is which path or route will be the best to use i.e., the path with the least cost. 

- This is determined using the routing process. 

- The best path thus obtained is called the optimal route. 

- Today, we have a number of algorithms available for determining the optimal path. 

These algorithms have been classified in to two major types:

1. Non – adaptive or static algorithms
2. Adaptive or dynamic algorithms

Concept of Optimality Principle

- This is the principle followed while determining the optimal router between the two routes. 

The general statement of the principle of optimality is stated below:

“An optimal policy has the property that whatever the initial state and initial decision are, the remaining decision must constitute an optimal policy with regard to the state resulting from the first decision.”

- This means if P is an optimal state that results in another state say Q, and then the portion of the original from that state to this state i.e., from P to Q must be optimum. 

- This only means the optimality of the part of the optimal policy is preserved. - The initial state and the final state are the most important parts of the optimum. 

- Consider an example, suppose we have problem with 3 inputs and 26 states. - Here, the state is associated with the optimum and the total cost is associated with the optimum policy.

- If brute force method is used for 3 inputs and 100 stages we have the total number of computations as 3¹⁰⁰. 

- That means for solving this problem, a super computer is required.

- Therefore, the approach used for solving this problem is a parallel processing approach. 

- Here, for the each state the least step is computed and stored during the programming. 

- This reduces the number of possibilities and hence reducing the amount of computation.

- The problems become complex if the initial and the final states are undefined. - It is necessary for the problem to follow the principle of optimality in order to use the dynamic programming. 

- This implies that whatever the state may be, the decisions that follow must be optimal in regard with the state obtained from the previous decision. 

- This property is found in combinatorial problems but since they use a lot of time and memory, this method is inefficient for them. 

- These problems can be solved efficiently if some sort of best first search and pruning technique is applied.

- In regard to the routing in networks, it follows from the optimality principle if a router B lies between router A and C which lie on an optimal path, then the path between the router B and C is also an optimal path and lies on the same path. 

- Sink tree is formed as a result of all optimal routes which is the ultimate goal of all the routing algorithms.